package _05_二叉树;

import java.util.Stack;

public class _剑指_Offer_36二叉搜索树与双向链表 {

    private Node prev, head;

    public Node treeToDoublyList(Node root) {
        if (root == null) return root;
        process(root);
        // 对首位
        head.left = prev;
        prev.right = head;
        return head;
    }

    // 中序遍历
    public void process(Node node) {
        if (node == null) return;
        process(node.left);
        // 连接节点
        if (prev != null) {
            prev.right = node;
            node.left = prev;
        } else {
            head = node;
        }
        prev = node;
        process(node.right);

    }

    public Node treeToDoublyList1(Node root) {
        if (root == null) return root;
        Node minNode = root;
        Node maxNode = root;
        Node prev = null;
        Stack<Node> stack = new Stack<>();
        while (true) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                if (stack.isEmpty()) {
                    break;
                } else {
                    // 弹出元素
                    Node node = stack.pop();
                    maxNode = node;
                    if (prev != null) {
                        prev.right = node;
                        node.left = prev;
                    } else {
                        minNode = node;
                    }
                    // 记录上次的值
                    prev = node;
                    if (node.right != null) {
                        root = node.right;
                    }
                }
            }

        }
        // 对首位
        minNode.left = maxNode;
        maxNode.right = minNode;
        return minNode;
    }
}
